// 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
// 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
// nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
// 输入: nums1 = `[4,1,2]`, nums2 = `[1,3,4,2]`.
// 输出: `[-1,3,-1]`
// 解释:
// 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
// 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
// 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

// 思路，单调栈
// 单调栈的元素从栈底到栈顶 ，递增还是递减，单调栈存储的是元素下标索引
//  如果要找元素右边第一个更大的元素，则需要维护单调递减栈，因为当前元素大于栈顶元素时，单调栈出栈，直到栈顶大于当前元素
//  如果要找元素右边第一个更小的元素，则需要维护单调递增栈，因为当前元素小于栈顶元素时，单调栈出栈，直到栈顶小于当前元素

function nextGreaterElement(nums1, nums2) {
    let result = new Array(nums1.length).fill(-1)
    let map = new Map()
    for (let i = 0; i < nums1.length; i++) {
        map.set(nums1[i], i)        
    }
    let stack = [0]
    for (let i = 0; i < nums2.length; i++) {
        while (stack.length && nums2[stack[stack.length - 1]] < nums2[i]) {
            let index = stack.pop()
            if (map.has(nums2[index])) {
                result[map.get(nums2[index])] = nums2[i]
            }
        }  
        stack.push(i)      
    }
    return result
}

let nums1 = [4,1,2], nums2 = [1,3,4,2]
console.log(nextGreaterElement(nums1, nums2))